//
// Created by postgres on 5/15/17.
//
#include "../include/08search/BinarySortTree.h"
/* 递归查找二叉排序树T中是否存在key, */
/* 指针parent指向最后查找结点的双亲*/
/* 若查找成功，则指针p指向该数据元素结点，并返回TRUE */
/* 否则指针p指向查找路径上访问的最后一个结点并返回FALSE */
Status SearchBST(BiSearchTree *T, BiSearchTree *parent,int key, BiSearchTree *node) {
    if (!(*T)) {
        node = NULL;
        return FALSE;
    } else if (key == (*T)->data) {
        *node = (*T);
        return TRUE;
    } else if (key < (*T)->data) {
        *parent=(*T);
        SearchBST(&(*T)->lchild,parent ,key, node);
    } else if (key > (*T)->data) {
        *parent=(*T);
        SearchBST(&(*T)->rchild, parent,key, node);
    }
}
Status DeleteNode(BiSearchTree *t){
    BiSearchTree p,s;
    if(!(*t)->lchild){
        p=*t;
        (*t)=(*t)->rchild;
        pfree(p);
    }else if(!(*t)->rchild){
        p=*t;
        (*t)=(*t)->lchild;
        pfree(p);
    } else{
        p=(*t)->lchild;
        while(p->rchild)
            p=p->rchild;
        (*t)->data=p->data;
        s=p;
        p=p->lchild;
        pfree(s);
    }

}
Status DeleteBST(BiSearchTree *T,int key){
    if (!(*T)) {
        return FALSE;
    } else if (key == (*T)->data) {
        DeleteNode(T);
        return TRUE;
    } else if (key < (*T)->data) {
        DeleteBST(&(*T)->lchild, key);
    } else if (key > (*T)->data) {
        DeleteBST(&(*T)->rchild,key);
    }
}
/*  当二叉排序树T中不存在关键字等于key的数据元素时， */
/*  插入key并返回TRUE，否则返回FALSE */
Status InsertBST(BiSearchTree *T, int key)
{
    BiSearchTree p,parent;
    if(!SearchBST(T,&parent,key,&p)){
        p=(BiSearchTree)palloc(sizeof(BiNode));
        p->data=key;
        p->lchild=NULL;
        p->rchild=NULL;
        if(!(*T))
            *T=p;
        else if(key < parent->data){
            parent->lchild=p;
        }else if(key > parent->data){
            parent->rchild=p;
        }
        return TRUE;
    }else{
        return  FALSE;
    }
}
void InitBiSortTree(BiSearchTree *t){
    *t=NULL;
}
void BiSearchTree_main()
{
    int i;
    int a[10]={62,88,58,47,35,73,51,99,37,93};
    BiSearchTree T;
    InitBiSortTree(&T);
    for(i=0;i<10;i++)
    {
        InsertBST(&T, a[i]);
    }
    //DeleteBST(&T,93);
    //DeleteBST(&T,37);
    DeleteBST(&T,47);
    printf("本样例建议断点跟踪查看二叉排序树结构");

}
